public class List {
	private No first = null;

	public void add(String value) {
		No no = new No();
		no.setElement(value);

		if (first == null)
			first = no;
		else {
			No last = first;
			while (last.getNext() != null)
				last = last.getNext();
			last.setNext(no);
		}
	}

	public void print() {
		No n = this.first;
		System.out.print(n.getElement() + " ");
		while (n.getNext() != null) {
			n = n.getNext();
			System.out.print(n.getElement() + " ");			
		}
		System.out.print(" ");
	}

	public long sort() {
		boolean houveTroca = false;
		No n = null;
		No anterior = null;
		long start, end;
		
		// Imprimindo lista desordenada
		System.out.print("Antes: ");
		print();
		
		start = System.currentTimeMillis();
		
		do{			
			houveTroca = false;			
			n = first;
			anterior = null;
			
			while(n != null && n.getNext() != null){				
				String valueA = n.getElement();
				String valueB = n.getNext().getElement();

				if(valueA.compareTo(valueB) > 0){
					No proximo = n.getNext();
					No atual = n;
					if(first == n)
						first = n.getNext();
					
					atual.setNext(proximo.getNext());
					proximo.setNext(atual);					
					
					if(anterior != null )
						anterior.setNext(proximo);
										
					houveTroca = true;	

					anterior = n;
					n = proximo;
				}
				else{
					anterior = n;
					n = n.getNext();
				}
			}
		}while(houveTroca);
		
		end = System.currentTimeMillis();
		
		// Imprimindo lista ordenada
		System.out.print("\tDepois: ");
		print();
		System.out.println("");
		
		return end - start;
	}
}